//
//  Problem718.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/21.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 718. 最长重复子数组
 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 示例：
   输入：
     A: [1,2,3,2,1]
     B: [3,2,1,4,7]
   输出：3
     解释：
     长度最长的公共子数组是 [3, 2, 1] 。
 提示：

 1 <= len(A), len(B) <= 1000
 0 <= A[i], B[i] < 100
 */
@objcMembers class Problem718: NSObject {
    func solution() {
        print(findLengthDClear([1,2,3,2,1], [3,2,1,4,7]))
        print(findLengthDClear([1,2,3,2,1], [1,2,1,1,1]))
        print(findLengthDClear([0,0,0,0,0], [0,0,0,0,0]))
        print(findLengthDClear([0,0,0,0,1], [1,0,0,0,0]))
    }
    
    /*
     1: 创建2个指针，f指向A头部，s指向B尾部
     2: 从这2个指针开始遍历数组：判断当前A与B相同子数组的长度
     3: 开始滑动，s往后推一步，f不动，再次执行步骤2
     4: 当s=0时，s不动，f向前走一步，执行步骤2
     5: 如果最大的长度已经超过未滑动的区间，那么不必在滑动了
     ```
     1 2 3 2 1
             3 2 1 4 7
     1 2 3 2 1
           3 2 1 4 7

     ......

     1 2 3 2 1
     3 2 1 4 7
          
     1 2 3 2 1
       3 2 1 4 7
          
     1 2 3 2 1
         3 2 1 4 7
     ```

     */
    func findLength(_ A: [Int], _ B: [Int]) -> Int {
        var f = 0, s = B.count
        var maxValue = 0
        var cur = 0
        while A.count - f > maxValue {
            if s == 0 {
                f += 1
            } else {
                s -= 1
            }
            
            cur = 0
            var ts = s
            for i in f..<A.count {
                if ts >= B.count {
                    break
                }
                if A[i] == B[ts] {
                    cur += 1
                } else {
                    maxValue = max(maxValue, cur)
                    cur = 0
                }
                ts += 1
            }
            maxValue = max(maxValue, cur)
        }
        
        return maxValue
    }
    
    /*
     动态规划
     1: 创建一个二维数组dp[A.len][B.len]
     2: dp[i][j]: 在A中以i为开头 在B中以j为开头，该处最长子数组的长度（该子数组 必须以i和j开头）
     3: 如果: A[i] == B[j] => dp[i][j] = 1 + dp[i+1][j+1]
     4: 如果: A[i] != B[j] => dp[i][j] = 0
     5: 我们要求的值，就是dp数组中的最大值
     */
    func findLengthD(_ A: [Int], _ B: [Int]) -> Int {
       var maxValue = 0
       var dp:[[Int]] = Array(repeating: Array(repeating: 0, count: B.count), count: A.count)
       for i in (0..<A.count).reversed() {
           for j in (0..<B.count).reversed() {
               if A[i] == B[j] {
                   if i + 1 < A.count, j + 1 < B.count {
                       dp[i][j] = 1 + dp[i+1][j+1]
                   } else {
                       dp[i][j] = 1
                   }
               } else {
                   dp[i][j] = 0
               }
               maxValue = max(maxValue, dp[i][j])
           }
       }
       return maxValue
   }
    
    /*
     动态规划：优化数组
     优化：我们遍历时，都是让i保持一致，然后遍历j的，基于此，我们可以将二维简化为一维
     1: 创建2个临时变量，t和p
     2: p记录 上一次遍历，当前节点j后面的一位的信息
     3: t记录 上一次遍历，当前节点j的信息
     */
    func findLengthDClear(_ A: [Int], _ B: [Int]) -> Int {
        var maxValue = 0
        var dp:[Int] = Array(repeating: 0, count: B.count)
        for i in (0..<A.count).reversed() {
            var t = 0   // 记录上一个位置
            var p = 0
            for j in (0..<B.count).reversed() {
                p = t       // 上一个位置
                t = dp[j]
                if A[i] == B[j] {
                    dp[j] = 1 + p
                } else {
                    dp[j] = 0
                }
                maxValue = max(maxValue, dp[j])
            }
        }
        return maxValue
    }
}
